// https://leetcode.cn/problems/sum-root-to-leaf-numbers/

// 题干：给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
//       每条从根节点到叶节点的路径都代表一个数字：
//       例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
//       计算从根节点到叶节点生成的 所有数字之和 。
//       叶节点 是指没有子节点的节点。

// 示例：输入：root = [1,2,3]
//       输出：25

// 碎语：题目的参数不够，还是需要自己设置一个新函数
//       本题中，需要向左右子树传递信息，同时也要在回溯时收到子节点的值
//       前序遍历，本题递归结束条件位置特殊，还是需要微观
//       子节点的状态依赖于父节点

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    int sumNumbers(TreeNode* root)
    {
        return dfs(root, 0);
    }

    int dfs(TreeNode* root, int presum)
    {
        int ret = 0;
        presum = presum * 10 + root->val;

        // 注意是要且，到叶子节点才能返回
        if (root->left == nullptr && root->right == nullptr) return presum;

        if (root->left) ret += dfs(root->left, presum);
        if (root->right) ret += dfs(root->right, presum);

        return  ret;
    }
};

int main()
{
    Solution sol;

    auto root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);

    cout << sol.sumNumbers(root) << " ";
    cout << endl;

    return 0;
}